/* This Bignum library does not support negative number, division, modulo,...*/
const int base = 10000;
const int numdigit = 33;
struct bignum
{
    int digit[numdigit];
    int digitcount;
    bignum (int x = 0)
    {
        digitcount = 0;
        clear0(digit);
        for (; x; x/=base)
            digit[digitcount++] = x % base;
        if (!digitcount) digitcount++;
    }
    friend bignum operator +(const  bignum &a, const bignum &b);
    friend bignum operator -(const  bignum &a, const bignum &b);
    friend bignum operator *(const  bignum &a, const bignum &b);

    bignum operator +=(const bignum &a)
    {
        *this = *this + a;
        return *this;
    }

    bignum operator -=(const bignum &a)
    {
        *this = *this - a;
        return *this;
    }

    bignum operator *=(const bignum &a)
    {
        *this = *this * a;
        return *this;
    }

    void PrintBigNum(bool newline = true)
    {
        cout << digit[digitcount-1];
        ford(i,digitcount-2,0)
        {
            for(int PowerOfTen = base / 10; PowerOfTen; PowerOfTen /= 10)
            {
                if (digit[i] >= PowerOfTen) break;
                cout << 0;
            }
            cout << digit[i];
        }
        if (newline) cout << '\n';
    }

    bool operator ==(const bignum &a)
    {
        return CompareBigNum(*this,a) == 0;
    }

    bool operator <(const bignum &a)
    {
        return CompareBigNum(*this,a) == -1;
    }

    bool operator >(const bignum &a)
    {
        return CompareBigNum(*this,a) == 1;
    }

    bool operator !=(const bignum &a)
    {
        return CompareBigNum(*this,a) != 0;
    }

    bool operator <=(const bignum &a)
    {
        return CompareBigNum(*this,a) <= 0;
    }

    bool operator >=(const bignum &a)
    {
        return CompareBigNum(*this,a) >= 0;
    }

    private: int CompareBigNum(const bignum &a, const bignum &b)
    {
        if (a.digitcount < b.digitcount) return -1;
        if (a.digitcount > b.digitcount) return 1;
        int i = 0;
        while (i < a.digitcount-1 && a.digit[i] == b.digit[i])
            i++;
        return (a.digit[i]>b.digit[i])-(a.digit[i]-b.digit[i]);
    }
};

bignum operator +(const  bignum &a, const bignum &b)
{
    bignum result;
    result.digitcount = max(a.digitcount, b.digitcount);
    int memo = 0;
    forn(i,result.digitcount)
    {
        result.digit[i] = a.digit[i] + b.digit[i] + memo;
        if (result.digit[i] >= base)
        {
            result.digit[i] -= base;
            memo = 1;
        }
        else memo = 0;
    }
    if (memo) result.digit[result.digitcount++] = memo;
    return result;
}

bignum operator -(const  bignum &a, const bignum &b) //a>b
{
    bignum result;
    result.digitcount = a.digitcount;
    int memo = 0;
    forn(i,result.digitcount)
    {
        result.digit[i] = a.digit[i] - b.digit[i] - memo;
        if (result.digit[i] < 0)
        {
            result.digit[i] += base;
            memo = 1;
        }
        else memo = 0;
    }
    while (!result.digit[result.digitcount - 1]) result.digit[--result.digitcount] = 0;
    return result;
}

bignum operator *(const  bignum &a, const bignum &b)
{
    bignum result;
    result.digitcount = a.digitcount + b.digitcount - 1;
    int memo = 0;
    forn(i,a.digitcount) forn(j,b.digitcount)
        result.digit[i + j] += a.digit[i] * b.digit[j];
    forn(i,result.digitcount)
    {
        result.digit[i] += memo;
        memo = result.digit[i] / base;
        result.digit[i] %= base;
    }
    if (memo) result.digit[result.digitcount++] = memo;
    return result;
}
